/**
 * Copyright (c) 2020-2024, huli.com
 * All rights reserved.
 */
package com.xiaohujr.xuexue.leetcode.tree;

/**
 * https://leetcode-cn.com/problems/maximum-binary-tree-ii/
 *
 * @author Xue Xue (xuexue1@huli.com)
 * @version 1.0
 * @since 2020/12/18
 */
public class Q998 {
    int status = 0;

    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        if (root == null || root.val < val) {
            TreeNode tmp = new TreeNode(val);
            tmp.left = root;
            return tmp;
        }
        TreeNode right = insertIntoMaxTree(root, val);
        root.right = right;
        return root;
    }

    public TreeNode insertIntoMaxTree2(TreeNode root, int val) {
        TreeNode treeNode = new TreeNode(val);
        if (root == null) {
            return treeNode;
        }
        if (root.val < val) {
            treeNode.left = root;
            return treeNode;
        }
        TreeNode right = insertIntoMaxTree2(root.right, val);
        root.right = right;
        return root;
    }
}
